'''
@Author: shj
@Date: 2020-06-02 11:26:14
@LastEditTime: 2020-06-03 10:40:58
@LastEditors: shj
@Description:  反转链表
@FilePath: /python3/algorithms/offer_code/15_reverse_linked_list.py
'''
'''
题目描述
输入一个链表，反转链表后，输出新链表的表头。

思路 
利用链表的特性（相邻节点间通过指针定位）

注意：题目中默认的列表为无头节点
当链表长度<2时，不必反转，直接返回
取正向链表为link，反向链表为re_link，初始时正向链表link的指针指向第一个节点（first）即cur = first，其前置节点pre = None, 后置节点nex = cur.next
开始反转：
    1) 记录当前节点的后置节点 nex = cur.next，防止链表断开
注意：一定要先记录后置节点
    2) 将当前节点的后置指针指向其前置节点cur.next = pre
    3) 向后移动当前节点及其前置节点的指针 pre = cur, cur = nex
    4) 重复1-3,直到cur为空节点 while cur != None
    5) 返回当前节点的前置节点（表头节点） return pre
'''


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 链表长度小于2,不必反转，直接返回
        if pHead is None or pHead.next is None:
            return pHead
        pre = None  # 前置指针
        nex = None  # 后置指针
        cur = pHead  # 当前指针
        while cur != None:  # 反转完成
            nex = cur.next  # 必须先记录后置节点，防止断链
            cur.next = pre  # 反转
            # 指针后移
            pre = cur
            cur = nex
        # 反转完，返回表头
        return pre
